home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr53 / pctv4n_1.zip / LINKLIST.PAS < prev    next >
Pascal/Delphi Source File  |  1993-06-10  |  14KB  |  331 lines
  1. UNIT LinkList;
  2.  {$X+}                    { Allow function calls as "procedures" }
  3. {----------------------------------------------------------------
  4.  This unit provides a base "linked list" object that can be used
  5.  for linked records and objects.  The data and methods in the
  6.  base object take care of the linked list management functions.
  7. ----------------------------------------------------------------}
  8. INTERFACE
  9. TYPE
  10.   PLinkNode = ^TLinkNode; {-------------- LINKED LIST NODE TYPE }
  11.   TLinkNode = RECORD
  12.     PrevNode : PLinkNode;                { Previous linked node }
  13.     TheItem  : Pointer;                { Pointer to linked item }
  14.     NextNode : PLinkNode;                    { Next linked node }
  15.   END;
  16.  
  17.   PLinkList = ^TLinkList; {------------ LINKED LIST OBJECT TYPE }
  18.   TLinkList = OBJECT
  19.     NumNodes : Integer;                    { Current node count }
  20.     BaseNode : PLinkNode;                       { Starting node }
  21.     CONSTRUCTOR Init;
  22.     DESTRUCTOR  Done; VIRTUAL;
  23.            FUNCTION    ItemCount : Integer;
  24.            FUNCTION    ItemIndex(Item : Pointer) : Integer;
  25.            FUNCTION    ListEmpty : Boolean;
  26.             FUNCTION    FirstItem : Pointer;
  27.            FUNCTION    LastItem : Pointer;
  28.            FUNCTION    LastNode : PLinkNode;
  29.            FUNCTION    NodeForIndex(Index : Integer) : PLinkNode;
  30.            FUNCTION    NodeForItem(Item : Pointer) : PLinkNode;
  31.            FUNCTION    ItemForIndex(Index : Integer) : Pointer;
  32.            FUNCTION    AppendItem(Item : Pointer) : Boolean;
  33.            FUNCTION    DeleteItem(Item : Pointer) : Boolean;
  34.           FUNCTION    DeleteIndex(Index : Integer) : Boolean;
  35.            FUNCTION    InsertBefore(Target,Item : Pointer) : Boolean;
  36.             FUNCTION    InsertAfter(Target,Item : Pointer) : Boolean;
  37.            FUNCTION    DeleteAll : Boolean;
  38.         END;
  39.  
  40. IMPLEMENTATION
  41.  
  42. CONSTRUCTOR TLinkList.Init;
  43.  {Initialize a new TLinkList object and set up a null BaseNode.}
  44. BEGIN
  45.   BaseNode := NIL;
  46.   NumNodes := 0;
  47. END; {---------------------------------------- CONSTRUCTOR Init }
  48.  
  49. DESTRUCTOR TLinkList.Done;
  50.  {Disposes of a TLinkList object and its linked records.}
  51. VAR AThis,APrev : PLinkNode;
  52. BEGIN
  53.   DeleteAll;
  54. END; {----------------------------------------- DESTRUCTOR Done }
  55.  
  56. FUNCTION TLinkList.ItemIndex(Item : Pointer) : Integer;
  57.  {Returns the index of the "Item" or -1 if not in the list.}
  58. VAR AThis : PLinkNode;
  59.     NItem : Integer;
  60. BEGIN
  61.   IF (NumNodes = 0) THEN BEGIN       { If the list is empty,... }
  62.     ItemIndex := -1;                         { ... return "-1." }
  63.     Exit;
  64.   END;
  65.   FOR NItem := 0 TO NumNodes DO BEGIN     { See if item on list }
  66.     AThis := NodeForIndex(NItem);
  67.     IF (AThis^.TheItem = Item) THEN BEGIN   { YES: Return index }
  68.       ItemIndex := NItem;
  69.       Exit;
  70.     END;
  71.   END;
  72.   ItemIndex := -1;                              { NO: Return -1 }
  73. END; {------------------------------------ FUNCTION ItemIndex() }
  74.  
  75. FUNCTION TLinkList.ItemCount : Integer;
  76.  {Returns the number of items currently in the linked list.}
  77. BEGIN
  78.   ItemCount := NumNodes;
  79. END; {-------------------------------------- FUNCTION ItemCount }
  80.  
  81. FUNCTION TLinkList.ListEmpty : Boolean;
  82.  {Returns TRUE if the list is empty (i.e., BaseNode^.TheItem = NIL)}
  83. BEGIN
  84.   ListEmpty := (NumNodes = 0);
  85. END; {-------------------------------------- FUNCTION ListEmpty }
  86.  
  87. FUNCTION TLinkList.FirstItem : Pointer;
  88.  {Returns the pointer to the first item in the linked list.}
  89. BEGIN
  90.   FirstItem := BaseNode^.TheItem;
  91. END; {-------------------------------------- FUNCTION FirstItem }
  92.  
  93. FUNCTION TLinkList.LastItem : Pointer;
  94.  {Returns the pointer to the last item in the linked list.}
  95.  
  96. BEGIN
  97.   LastItem := LastNode^.TheItem;
  98. END; {--------------------------------------- FUNCTION LastItem }
  99.  
  100. FUNCTION TLinkList.LastNode : PLinkNode;
  101.  {Returns the pointer to the last link in the chain.}
  102. VAR AThis, ANext : PLinkNode;
  103. BEGIN
  104.   ANext := BaseNode;
  105.   WHILE (ANext <> NIL) DO BEGIN
  106.     AThis := ANext;
  107.     ANext := AThis^.NextNode;
  108.   END;
  109.   LastNode := AThis;
  110. END; {--------------------------------------- FUNCTION LastNode }
  111.  
  112. FUNCTION TLinkList.NodeForIndex(Index : Integer) : PLinkNode;
  113. {----------------------------------------------------------------
  114.  Returns the pointer to the link node for a given item index.
  115.  (Returns NIL if "Index" is not in range [0..NumNodes].
  116. ----------------------------------------------------------------}
  117. VAR AThis, ANext : PLinkNode;
  118.     N : Integer;
  119. BEGIN
  120.   IF ((Index < 0) OR (Index > NumNodes)) THEN BEGIN { Index bad?}
  121.     NodeForIndex := NIL;                      { YES: Return NIL }
  122.     Exit;
  123.   END;
  124.   ANext := BaseNode;                     { Starting at base,... }
  125.   FOR N := 0 TO Index DO BEGIN             { ...get the node... }
  126.     AThis := ANext;                     {... having this index. }
  127.     ANext := AThis^.NextNode;
  128.   END;
  129.   NodeForIndex := AThis;
  130. END; {--------------------------------- FUNCTION NodeForIndex() }
  131.  
  132. FUNCTION TLinkList.NodeForItem(Item : Pointer) : PLinkNode;
  133. {----------------------------------------------------------------
  134.  Returns the pointer to the link item for "Item."
  135.  (Returns NIL if "Item" is not in the list.)
  136. ----------------------------------------------------------------}
  137. VAR AThis, ANext : PLinkNode;
  138. BEGIN
  139.   IF (Item = NIL) THEN BEGIN       { Return NIL for a NIL item. }
  140.     NodeForItem := NIL;
  141.     Exit;
  142.   END;
  143.   ANext := BaseNode;                      { Starting at base... }
  144.   WHILE (ANext <> NIL) DO BEGIN        { ...look for a match... }
  145.     AThis := ANext;                         { ...with "Item"... }
  146.     ANext := AThis^.NextNode;
  147.     IF (AThis^.TheItem = Item) THEN BEGIN           { MATCH:... }
  148.       NodeForItem := AThis;               { Return node pointer }
  149.       Exit;
  150.     END;
  151.   END;
  152.   NodeForItem := NIL;                    { NO MATCH: Return NIL }
  153. END; {---------------------------------- FUNCTION NodeForItem() }
  154.  
  155. FUNCTION TLinkList.ItemForIndex(Index : Integer) : Pointer;
  156. {----------------------------------------------------------------
  157.  Returns the pointer to the item for a given item index.
  158.  (Returns NIL if "Index" is not in range [0..NumNodes].
  159. ----------------------------------------------------------------}
  160. VAR AThis : PLinkNode;
  161. BEGIN
  162.   AThis := NodeForIndex(Index);  { Get node pointer for "Index" }
  163.   IF (AThis <> NIL) THEN                       { FOUND NODE:... }
  164.     ItemForIndex := AThis^.TheItem     { ...return item pointer }
  165.   ELSE
  166.     ItemForIndex := NIL;                  { NO NODE: Return NIL }
  167. END; {--------------------------------- FUNCTION ItemForIndex() }
  168.  
  169. FUNCTION TLinkList.AppendItem(Item : Pointer) : Boolean;
  170. {----------------------------------------------------------------
  171.  Adds "Item" to the end of linked list and increments the count.
  172.  Returns TRUE if successful; FALSE if not.
  173.  NOTE: If "Item" is already in the list, it is deleted and moved
  174.   to the end list.  (This prevents the list from having duplicate         entries for the same Item.)
  175. ----------------------------------------------------------------}
  176. VAR AThis, ALast : PLinkNode;
  177. BEGIN
  178.   IF (NumNodes > 0) THEN                { If there are nodes... }
  179.     DeleteItem(Item);        { ...delete any existing "Item"... }
  180.   IF (MaxAvail > SizeOf(TLinkNode)) THEN BEGIN { Get node space }
  181.     GetMem(AThis,SizeOf(TLinkNode));
  182.     AThis^.TheItem := Item;             { Assign "Item" to node }
  183.     IF (NumNodes > 0) THEN BEGIN           { NOT FIRST NODE:... }
  184.       ALast := LastNode;       { Make "Item" node the last node }
  185.       AThis^.NextNode := NIL;
  186.       AThis^.TheItem  := Item;
  187.       AThis^.PrevNode := ALast;
  188.       ALast^.NextNode := AThis;
  189.     END
  190.     ELSE BEGIN                                 { FIRST NODE:... }
  191.       BaseNode := AThis;                      { ...Fix pointers }
  192.       AThis^.PrevNode := NIL;
  193.       AThis^.NextNode := NIL;
  194.     END;
  195.     Inc(NumNodes);                   { Increment the node count }
  196.     AppendItem := TRUE;                           { Return TRUE }
  197.   END
  198.   ELSE                                          { NO MEMORY:... }
  199.     AppendItem := FALSE;                      { ...Return FALSE }
  200. END; {----------------------------------- FUNCTION AppendItem() }
  201.  
  202. FUNCTION TLinkList.DeleteItem(Item : Pointer) : Boolean;
  203.  {Deletes "Item" from the linked list and decrements the item count.}
  204. VAR AThis : PLinkNode;
  205. BEGIN
  206.   AThis := NodeForItem(Item);     { Get node pointer for "Item" }
  207.   IF (AThis = NIL) THEN BEGIN                     { NO NODE:... }
  208.     DeleteItem := FALSE;                      { ...Return FALSE }
  209.     Exit;
  210.   END;
  211.   WITH AThis^ DO BEGIN                         { NODE FOUND:... }
  212.     IF (PrevNode <> NIL) THEN                { NOT BaseNode:... }
  213.       PrevNode^.NextNode := NextNode       { ...fix Prev's Next }
  214.     ELSE                                      { IS BaseNode:... }
  215.       BaseNode := NextNode;               { ...promote old Next }
  216.     IF (NextNode <> NIL) THEN               { NOT Last Node:... }
  217.       NextNode^.PrevNode := PrevNode;      { ...fix Next's Prev }
  218.   END;
  219.   FreeMem(AThis,SizeOf(TLinkNode));         { Deallocate memory }
  220.   Dec(NumNodes);                         { Decrement node count }
  221.   DeleteItem := TRUE;                             { Return TRUE }
  222. END; {----------------------------------- FUNCTION DeleteItem() }
  223.  
  224. FUNCTION TLinkList.DeleteIndex(Index : Integer) : Boolean;
  225. {----------------------------------------------------------------
  226.  Deletes Item number "Index" from the linked list and decrements
  227.  the item count.
  228.  NOTE: Returns FALSE if Index not in [0..NumNodes]
  229. ----------------------------------------------------------------}
  230. VAR AThis : PLinkNode;
  231. BEGIN
  232.   IF ((Index < 0) OR (Index > NumNodes)) THEN BEGIN { Bad Index? }
  233.     DeleteIndex := FALSE;                   { YES: Return FALSE }
  234.     Exit;
  235.   END;
  236.   DeleteIndex := DeleteItem(ItemForIndex(Index)); {Delete item...}
  237. END; {---------------------------------- FUNCTION DeleteIndex() }
  238.  
  239. FUNCTION TLinkList.InsertBefore(Target,Item : Pointer) : Boolean;
  240.  {Inserts "Item" BEFORE "Target" item.  If "Target" is not in
  241.  the linked list, "Item" is inserted at the head of the list.}
  242. VAR APrev, AThis, ANext : PLinkNode;
  243. BEGIN
  244.   IF (Item = NIL) THEN BEGIN                     { NIL Item:... }
  245.     InsertBefore := FALSE;                    { ...Return FALSE }
  246.     Exit;
  247.   END;
  248.   DeleteItem(Item);                  { Delete Item (if on list) }
  249.   IF (MaxAvail > SizeOf(TLinkNode)) THEN BEGIN    { If space... }
  250.     GetMem(AThis,SizeOf(TLinkNode));         { ...allocate node }
  251.     IF (Target = NIL) THEN                     { NIL Target:... }
  252.       ANext := BaseNode               { ...new node is BaseNode }
  253.     ELSE BEGIN                                   { Otherwise... }
  254.       ANext := NodeForItem(Target);        { ...get Target node }
  255.       IF (ANext = NIL) THEN                   { NIL Target: ... }
  256.         ANext := BaseNode;            { ...new node is BaseNode }
  257.     END;
  258.     WITH AThis^ DO BEGIN               { Now adjust pointers... }
  259.       APrev    := ANext^.PrevNode;
  260.       IF (APrev <> NIL) THEN
  261.         APrev^.NextNode := AThis;
  262.       PrevNode := APrev;
  263.       NextNode := ANext;
  264.       TheItem  := Item;
  265.       ANext^.PrevNode := AThis;
  266.     END;
  267.     IF (AThis^.PrevNode = NIL) THEN                 { 1st node? }
  268.       BaseNode := AThis;           { YES: assign it as BaseNode }
  269.     Inc(NumNodes);                       { Increment node count }
  270.     InsertBefore := TRUE;                         { Return TRUE }
  271.   END
  272.   ELSE                                         { NO MEMORY: ... }
  273.     InsertBefore := FALSE;                    { ...Return FALSE }
  274. END; {--------------------------------- FUNCTION InsertBefore() }
  275.  
  276. FUNCTION TLinkList.InsertAfter(Target,Item : Pointer) : Boolean;
  277. {Inserts "Item" AFTER "Target" item.  If "Target" is not in
  278.  the linked list, "Item" is inserted at the end of the list.}
  279. VAR APrev, AThis, ANext : PLinkNode;
  280. BEGIN
  281.   IF (Item = NIL) THEN BEGIN                     { NIL Item:... }
  282.     InsertAfter := FALSE;                     { ...Return FALSE }
  283.     Exit;
  284.   END;
  285.   DeleteItem(Item);                  { Delete Item (if on list) }
  286.   IF (MaxAvail > SizeOf(TLinkNode)) THEN BEGIN    { If space... }
  287.     GetMem(AThis,SizeOf(TLinkNode));         { ...allocate node }
  288.     IF (Target = NIL) THEN                     { NIL Target?... }
  289.       APrev := LastNode             { YES: Set Prev to LastNode }
  290.     ELSE BEGIN                                        { NO: ... }
  291.       APrev := NodeForItem(Target);        { Set Prev to Target }
  292.       IF (APrev = NIL) THEN                       { NIL Target? }
  293.         APrev := LastNode;          { YES: Set Prev to LastNode }
  294.     END;
  295.     WITH AThis^ DO BEGIN               { Now adjust pointers... }
  296.       ANext := APrev^.NextNode;
  297.       IF (ANext <> NIL) THEN
  298.         ANext^.PrevNode := AThis;
  299.       PrevNode := APrev;
  300.       NextNode := ANext;
  301.       TheItem  := Item;
  302.       APrev^.NextNode := AThis;
  303.     END;
  304.     Inc(NumNodes);                       { Increment node count }
  305.     InsertAfter := TRUE;                          { Return TRUE }
  306.   END
  307.   ELSE                                         { NO MEMORY: ... }
  308.     InsertAfter := FALSE;                     { ...Return FALSE }
  309. END; {---------------------------------- FUNCTION InsertAfter() }
  310.  
  311. FUNCTION TLinkList.DeleteAll : Boolean;
  312. {----------------------------------------------------------------
  313.  Disposes of all the link nodes, leaving set to NIL BaseNode.
  314.  Only return FALSE if one of the delete operations failed.
  315. ----------------------------------------------------------------}
  316. VAR GoodReturn : Boolean;
  317. BEGIN
  318.   GoodReturn := TRUE;                  { Assume we will succeed }
  319.   IF (NumNodes = 0) THEN BEGIN        { If the list is empty... }
  320.     BaseNode := NIL;                { ...ensure BaseNode is NIL }
  321.     DeleteAll := TRUE;                         { ...Return TRUE }
  322.     Exit;
  323.   END;
  324.   WHILE (NumNodes > 0) DO                 { List NOT empty: ... }
  325.     IF (NOT DeleteIndex(NumNodes-1)) THEN
  326.       GoodReturn := FALSE;                  { Delete failed (?) }
  327.   BaseNode := NIL;                     { Ensure BaseNode is NIL }
  328.   DeleteAll := GoodReturn;          { Reflect outcome in return }
  329. END; {-------------------------------------- FUNCTION DeleteAll }
  330. END. {------------------------------------------- UNIT LinkList }
  331.